package com.lw.leetcode.sort.c;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer II 114. 外星文字典
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/31 9:08
 */
public class AlienOrder {

    public static void main(String[] args) {
        AlienOrder test = new AlienOrder();

        // "wertf"
//        String[] arr = {"wrt", "wrf", "er", "ett", "rftt"};

        // "zx"
//        String[] arr = {"z", "x"};

        // ""
//        String[] arr = {"z", "x", "z"};

        // "acbz"
//        String[] arr = {"ac","ab","zc","zb"};

        // "wertf"
        String[] arr = {"wrt", "wrf", "er", "ett", "rftt"};


        String s = test.alienOrder(arr);
        System.out.println(s);
    }


    private Map<Integer, Set<Integer>> gtMap = new HashMap<>();

    public String alienOrder(String[] words) {
        int[][] arr = new int[26][26];
        int[] flag = new int[26];
        int length = words.length;
        for (String word : words) {
            int l = word.length();
            for (int j = 0; j < l; j++) {
                flag[word.charAt(j) - 'a'] = 1;
            }
        }
        for (int i = 1; i < length; i++) {
            String word = words[i];
            String last = words[i - 1];
            int l = Math.min(word.length(), last.length());
            boolean boo = false;
            for (int j = 0; j < l; j++) {
                int a = word.charAt(j) - 'a';
                int b = last.charAt(j) - 'a';
                if (a != b) {
                    gtMap.computeIfAbsent(a, v -> new HashSet<>()).add(b);
                    boo = true;
                    break;
                }
            }
            if (!boo && word.length() < last.length()) {
                return "";
            }
        }
        for (int i = 0; i < 26; i++) {
            int[] ints = arr[i];
            if (find(ints, i, i)) {
                return "";
            }
        }
        int count = 0;
        for (int i : flag) {
            if (i == 1) {
                count++;
            }
        }
        int[] items = new int[count];
        int index = 0;
        for (int k = 0; k < 26; k++) {
            if (flag[k] == 1) {
                items[index++] = k;
            }
        }
        sort(items, arr, 0, count - 1);
        StringBuilder sb = new StringBuilder(count);
        for (int item : items) {
            sb.append((char) (item + 'a'));
        }
        return sb.toString();
    }

    private void sort(int[] items, int[][] arr, int st, int end) {
        if (st >= end) {
            return;
        }
        int f = items[st];
        int[] ints = arr[f];
        int a = st + 1;
        int b = end;
        while (a <= b) {
            int item = items[a];
            if (ints[item] == 1) {
                items[a - 1] = item;
                items[a] = f;
                a++;
            } else {
                items[a] = items[b];
                items[b] = item;
                b--;
            }
        }
        sort(items, arr, st, a - 2);
        sort(items, arr, a, end);
    }

    private boolean find(int[] ints, int item, int f) {
        Set<Integer> set = gtMap.get(item);
        if (set == null) {
            return false;
        }
        for (int i : set) {
            if (i == f) {
                return true;
            }
            if (ints[i] == 1) {
                continue;
            }
            ints[i] = 1;
            if (find(ints, i, f)) {
                return true;
            }
        }
        return false;
    }

}
